#include<iostream>
#include<vector>
using namespace std;
/*
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
解题思路：
与股票买卖1不同的是股票买卖2允许股票买卖多次
同样设dp数组dp[i][0]表示持有股票的手中最大现金
dp[i][1]表示不持有股票的手中最大现金
不持有股票时手中的最大现金可以由前一天就不持有股票或者当前卖出股票得来dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
持有股票时手中的最大现金可以由前一天就持有股票的手中的最大现金和在当天购入股票的最大现金得来
但是需要注意，在当天购入股票时手上的本金并非是0而是之前卖出股票所获得的最大利润dp[i-1][1]
dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])
*/
int dp(vector<int> prices)
{
    //创建dp数组并初始化
    vector<vector<int>> dp(prices.size(),vector<int>(2));
    dp[0][0]=-prices[0];
    dp[0][1] = 0;
    for(int i=1;i<prices.size();i++)
    {
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]);
        dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
    }
    return dp[prices.size()-1][1];
}
int main()
{
    cout<<"enetr a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
    {
        cin>>nums[i];
    }
    cout<<dp(nums);
    return 0;
}